package com.example.wangzh.mytest.part.walker_algorithm;

import android.util.Log;

public class TreePositioner {
    private double levelSeparation = 100;
    private int maxDepth = 1000;
    private double siblingSeparation = 40;
    private double subtreeSeparation = 40;

    private PrevNodeEntity curPrevNodeEntity = new PrevNodeEntity();
    private double xTopAdjustment;
    private double yTopAdjustment;

    /**
     * 此函数确定树中每个节点的坐标.传入一个指向树顶节点的指针作为输入.这里假设顶节点的x和y坐标已按需设置,因为其下方的树将相对于这些坐标进行定位.如果无错误则返回TRUE,否则返回FALSE.
     *
     * @param node
     * @return
     */
    public boolean positionTree(Node node) {
        boolean result;
        if (node != null) {
            /*Initialize the list of previous nodes at each level. */
            initPrevNodeList();
            /*Do the preliminary positioning with a postorder wa1k.*/
            firstWalk(node, 0);
            /*Determine how to adjust all the nodes with respect to */
            /* the location of the root. */
            xTopAdjustment = node.getXCoord() - node.getPrelim();
            yTopAdjustment = node.getYCoord();
            /*Do the final positioning with a preorder walk.		  */
            result = secondWalk(node, 0, 0);
        } else {
            /*不重要的: return TRUE if a null pointer was passed.			*/
            result = true;
        }
        return result;
    }

    /**
     * 在第一次后序遍历中,为树中的每个节点分配一个初步的x坐标(存储在字段PRELIM(Node)中).此外,内部节点被赋予一个修饰值,这些修饰值将用于将其子节点向右移动(存储在字段MODIFIER(Node)中).
     *
     * @param node
     * @param level
     */
    private void firstWalk(Node node, int level) {
        /*Set the pointer to the previous node at this level. */
        node.setLeftNeighbor(getPrevNodeAtLevel(level));
        setPrevNodeAtLevel(level, node);/* This is now the previous. */
        node.setModifier(0);/*Set the default modifier value. */
//        Log.i("wzh", "first walk.node:" + node.getName() + " level:" + level);

        if (node.isLeaf() || level == maxDepth) {
            if (node.hasLeftSibling()) {
                /* Determine the preliminary x-coordinate based on: */
                /* the preliminary x-coordinate of the left sibling, */
                /* the separation between sibling nodes, and 		*/
                /* the mean size of left sibling and current node. */
                //这个初步坐标似乎是相对于树顶节点的而非相对于根节点
                node.setPrelim(node.getLeftSibling().getPrelim() + siblingSeparation + meanNodeSize(node.getLeftSibling(), node));
            } else {
                /*No sibling on the left to worry about.			*/
                node.setPrelim(0);
            }
        } else {
            /* This Node is not a leaf, so call this procedure */
            /* recursively for each of its offspring. */
            Node leftmost = node.getFirstChild();
            Node rightmost = leftmost;

            firstWalk(leftmost, level + 1);

            while (rightmost.hasRightSibling()) {
                rightmost = rightmost.getRightSibling();
                firstWalk(rightmost, level + 1);
            }

            double midpoint = (leftmost.getPrelim() + rightmost.getPrelim()) / 2;

            if (node.hasLeftSibling()) {
                node.setPrelim(node.getLeftSibling().getPrelim() + siblingSeparation + meanNodeSize(node.getLeftSibling(), node));
                node.setModifier(node.getPrelim() - midpoint);
                apportion(node, level);
            } else {
                node.setPrelim(midpoint);
            }
        }
        Log.i("wzh", String.format("first walk end.node:%s prelim:%.0f modifier:%.0f", node.name, node.getPrelim(),
                node.getModifier()));
    }

    /**
     * 在第二次先序遍历中,通过将节点的初步x坐标与其所有祖先的修饰值相加,为每个节点分配最终的x坐标.y坐标取决于树的高度.如果内部节点的实际位置位于其初步位置的右侧,则以该节点为根的子树必须向右移动,以使子节点围绕父节点居中.为了避免立即调整子树中的所有节点,每个节点在修饰符字段(MODIFIER(Node))中记住到临时位置的距离(指的是第二步的操作?).在第二次遍历树时,修饰值被累积并应用于每个节点.如果无错误则返回TRUE,否则返回FALSE.
     *
     * @param node
     * @param level
     * @param modSum
     * @return
     */
    private boolean secondWalk(Node node, int level, double modSum) {
        boolean result = true;
        if (level <= maxDepth) {
            double xTemp = xTopAdjustment + node.getPrelim() + modSum;
            double yTemp = yTopAdjustment + (level * levelSeparation);
            /* Check to see that xTemp and yTemp are of the proper */
            /* size for your application. */
            if (checkExtentsRange(xTemp, yTemp)) {
                node.setXCoord(xTemp);
                node.setYCoord(yTemp);

                if (node.hasChild()) {
                    /*Apply the Modifier value for this node to */
                    /*all its offspring. */
                    result = secondWalk(node.getFirstChild(), level + 1, modSum + node.getModifier());
                }

                if (result && node.hasRightSibling()) {
                    result = secondWalk(node.getRightSibling(), level, modSum);
                }

            } else {
                /* Continuing would put the tree outside of the */
                /* drawable extents range. */
                result = false;
            }
        } else {
            /* We are at a level deeper than what we want to draw. */
            result = true;
        }
        Log.i("wzh", String.format("second walk end.node:%s xCoord:%.0f yCoord:%.0f", node.name, node.getXCoord(), node.getYCoord()));
        return result;
    }

    /**
     * 此过程清理了小型兄弟子树的定位,从而解决了早期算法中明显的"从左到右粘合"问题.当将一个新的子树逐渐向右移动时,可能会在之前被夹在较大子树之间的小型子树之间产生间隙.因此,在将新的较大子树向右移动时,其移动的距离也会分配给较小的内部子树,从而创建出美观的布局.
     *
     * @param node
     * @param level
     */
    private void apportion(Node node, int level) {
//        Log.i("wzh", "apportion.node:" + node.getName() + " level:" + level);
        Node leftmost = node.getFirstChild();
        Node neighbor = leftmost.getLeftNeighbor();
        int compareDepth = 1;
        int depthToStop = maxDepth - level;

        while (leftmost != null && neighbor != null && compareDepth <= depthToStop) {
            /* Compute the location of Leftmost and where it should */
            /* be with respect to Neighbor. */
            double leftModSum = 0;
            double rightModSum = 0;

            Node ancestorLeftmost = leftmost;
            Node ancestorNeighbor = neighbor;

            for (int i = 0; i < compareDepth; i++) {
                ancestorLeftmost = ancestorLeftmost.getParent();
                ancestorNeighbor = ancestorNeighbor.getParent();
                rightModSum += ancestorLeftmost.getModifier();
                leftModSum += ancestorNeighbor.getModifier();
            }
            /* Find the MoveDistance, and apply it to Node's subtree. */
            /*Add appropriate portions to smaller interior subtrees. */
            double moveDistance = (neighbor.getPrelim() + leftModSum + subtreeSeparation + meanNodeSize(leftmost, neighbor)) - (leftmost.getPrelim() + rightModSum);
//            Log.i("wzh", String.format("leftmost:%s neighbor:%s ancestorLeftMost:%s ancestorNeighbor:%s", leftmost.name
//                    , neighbor.name, ancestorLeftmost.name, ancestorNeighbor.name));
            if (moveDistance > 0) {
                /*Count interior sibling subtrees in LeftSiblings*/
                Node tempPtr = node;
                int leftSiblings = 0;

                while (tempPtr != null && tempPtr != ancestorNeighbor) {
                    leftSiblings++;
                    tempPtr = tempPtr.getLeftSibling();
                }

                if (tempPtr != null) {
                    /*Apply portions to appropriate leftsibling */
                    /* subtrees. */
                    double portion = moveDistance / leftSiblings;
                    tempPtr = node;

                    while (tempPtr != ancestorNeighbor) {
                        tempPtr.setPrelim(tempPtr.getPrelim() + moveDistance);
                        tempPtr.setModifier(tempPtr.getModifier() + moveDistance);
                        moveDistance -= portion;
                        tempPtr = tempPtr.getLeftSibling();
                    }
                } else {
                    /* Don't need to move anything--it needs to */
                    /* be done by an ancestor because */
                    /* AncestorNeighbor and AncestorLeftmost are */
                    /* not siblings of each other. */
                    return;
                }
            }

            /* Determine the leftmost descendant of Node at the next 	*/
            /* lower level to compare its positioning against that of	*/
            /* its Neighbor.											*/
            compareDepth++;
            if (leftmost.isLeaf()) {
                leftmost = getLeftmost(node, 0, compareDepth);
            } else {
                leftmost = leftmost.getFirstChild();
            }
            if (leftmost != null) {
                neighbor = leftmost.getLeftNeighbor();
            }
        }
    }

    /**
     * 此函数返回在给定深度下节点的最左后代.该功能通过后序遍历节点下的子树实现,遍历至指定深度.这里的深度并非两次主要树遍历中使用的绝对树层级,而是指在查找最左后代的节点之下的层级.
     *
     * @param node
     * @param level
     * @param depth
     * @return
     */
    private Node getLeftmost(Node node, int level, int depth) {
        if (level >= depth) {
            return node;
        } else if (node.isLeaf()) {
            return null;
        } else {
            Node rightmost = node.getFirstChild();
            Node leftmost = getLeftmost(rightmost, level + 1, depth);
            /* Do a postorder walk of the subtree below Node. */
            while (leftmost == null && rightmost.hasRightSibling()) {
                rightmost = rightmost.getRightSibling();
                leftmost = getLeftmost(rightmost, level + 1, depth);
            }

            return leftmost;
        }
    }

    /**
     * 此函数返回两个传入节点的平均大小.它将左侧节点右半部分的大小与右侧节点左半部分的大小相加.如果所有节点的大小相同,则这是一个简单的计算.
     *
     * @param leftNode
     * @param rightNode
     * @return
     */
    private double meanNodeSize(Node leftNode, Node rightNode) {
        double nodeSize = 0;
        if (leftNode != null) {
            nodeSize += leftNode.getRightSize();
        }
        if (rightNode != null) {
            nodeSize += rightNode.getLeftSize();
        }
        return nodeSize;
    }

    /**
     * 此函数验证传入的x和y坐标是否在用于绘图的坐标系范围内.例如,如果x和y坐标必须是2字节整数,则该函数可以判断xValue和yValue是否过大.
     *
     * @param xValue
     * @param yValue
     * @return
     */
    private boolean checkExtentsRange(double xValue, double yValue) {
        // 实现具体的范围检查逻辑
        return true;
    }

    /**
     * 初始化每一级的previous节点列表.三个列表维护过程——GETPREVNODEATLEVEL,SETPREVNODEATLEVEL和INITPREVNODELIST——维护一个单向链表.列表中的每个条目对应于给定级别中当前节点的前一个节点(例如,列表中的元素2对应于级别2中当前节点左侧的节点).如果最大树大小事先已知,则此列表可以替换为固定大小的数组,这些过程将变得简单.每个列表元素包含两个字段:PREVNODE——该级别的前一个节点,以及NEXTLEVEL——指向下一个列表元素的前向指针.为了性能考虑,在调用POSITIONTREE之间不需要清理该列表.
     */
    //初始化,把PrevNodeEntity链中的所有元素的prevNode置空
    private void initPrevNodeList() {
        /* Start with the node at level 0--the apex of the tree. */
        PrevNodeEntity tempEntity = curPrevNodeEntity;
        while (tempEntity != null) {
            tempEntity.prevNode = null;
            tempEntity = tempEntity.nextLevel;
        }
    }

    /**
     * 获取该级别的前一个节点.
     *
     * @param level
     * @return
     */
    private Node getPrevNodeAtLevel(int level) {
        /* Start with the node at level 0--the apex of the tree. */
        PrevNodeEntity tempEntity = curPrevNodeEntity;
        int i = 0;
        while (tempEntity != null) {
            if (i == level) {
                return tempEntity.getPrevNode();
            }
            tempEntity = tempEntity.nextLevel;
            i++;
        }
        /*Otherwise, there was no node at the specific level.	*/
        return null;
    }

    /**
     * 设置列表中的一个元素.参见第14页的图9.函数"ALLOCATE_A_NODE"(此处未展示)请求一个指向内存块的指针,该内存块将用于表示列表中的一个节点.
     *
     * @param level
     * @param node
     */
    private void setPrevNodeAtLevel(int level, Node node) {
        /* Start with the node at level 0--the apex of the tree. */
        PrevNodeEntity tempEntity = curPrevNodeEntity;
        int i = 0;
        while (tempEntity != null) {
            if (i == level) {
                /*At this level, replace the existing list */
                /*element with the passed-in node. */
                tempEntity.prevNode = node;
                return;
            } else if (tempEntity.nextLevel == null) {
                /*There isn't a list element yet at this level, so */
                /* add one. The following instructions prepare the */
                /* list element at the next level, not at this one. */
                PrevNodeEntity newEntity = new PrevNodeEntity();
                newEntity.prevNode = null;
                newEntity.nextLevel = null;
                tempEntity.nextLevel = newEntity;
            }
            /*Prepare to move to the next level, to look again. */
            tempEntity = tempEntity.nextLevel;
            i++;
        }

        /*Should only get here if LevelZeroPtr is nil.		*/
        //链为空时为什么不将其放在第level个而是放在第0个?可能是只有level为0时链才会为空
        PrevNodeEntity newEntity = new PrevNodeEntity();
        newEntity.prevNode = node;
        newEntity.nextLevel = null;
    }

    public static class PrevNodeEntity {
        Node prevNode;
        PrevNodeEntity nextLevel;

        public Node getPrevNode() {
            return prevNode;
        }

        public void setPrevNode(Node prevNode) {
            this.prevNode = prevNode;
        }

        public PrevNodeEntity getNextLevel() {
            return nextLevel;
        }

        public void setNextLevel(PrevNodeEntity nextLevel) {
            this.nextLevel = nextLevel;
        }
    }

    public static class Node {
        private String name;//名称
        private Node parent;//父节点
        private Node firstChild;//第一个子节点
        private Node leftSibling;//左兄弟节点
        private Node rightSibling;//右兄弟节点
        private Node leftNeighbor;//左侧的邻居节点,可以不是同一个子树
        private double xCoord;//最终x坐标
        private double yCoord;//最终y坐标
        private double prelim;//prelim是节点x坐标初步的值,随着逐步调整,最终变成最终值(未经父节点修正)
        private double modifier;//modifier是指以该节点为树顶节点的节点都需要左右移动的修正值,负则向左,正则向右
        private double leftSize = 10;//节点在节点坐标所在的点左边一侧的长度
        private double rightSize = 10;//节点在节点坐标坐标所在的点右边一侧的长度

        // Getters and setters for all fields


        public Node(String name) {
            this.name = name;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public Node getParent() {
            return parent;
        }

        public void setParent(Node parent) {
            this.parent = parent;
        }

        public Node getFirstChild() {
            return firstChild;
        }

        public void setFirstChild(Node firstChild) {
            this.firstChild = firstChild;
        }

        public Node getLeftSibling() {
            return leftSibling;
        }

        public void setLeftSibling(Node leftSibling) {
            this.leftSibling = leftSibling;
        }

        public Node getRightSibling() {
            return rightSibling;
        }

        public void setRightSibling(Node rightSibling) {
            this.rightSibling = rightSibling;
        }

        public Node getLeftNeighbor() {
            return leftNeighbor;
        }

        public void setLeftNeighbor(Node leftNeighbor) {
            this.leftNeighbor = leftNeighbor;
        }

        public double getXCoord() {
            return xCoord;
        }

        public void setXCoord(double xCoord) {
            this.xCoord = xCoord;
        }

        public double getYCoord() {
            return yCoord;
        }

        public void setYCoord(double yCoord) {
            this.yCoord = yCoord;
        }

        public double getPrelim() {
            return prelim;
        }

        public void setPrelim(double prelim) {
            this.prelim = prelim;
        }

        public double getModifier() {
            return modifier;
        }

        public void setModifier(double modifier) {
            this.modifier = modifier;
        }

        public double getLeftSize() {
            return leftSize;
        }

        public void setLeftSize(double leftSize) {
            this.leftSize = leftSize;
        }

        public double getRightSize() {
            return rightSize;
        }

        public void setRightSize(double rightSize) {
            this.rightSize = rightSize;
        }

        public boolean isLeaf() {
            return firstChild == null;
        }

        public boolean hasLeftSibling() {
            return leftSibling != null;
        }

        public boolean hasRightSibling() {
            return rightSibling != null;
        }

        public boolean hasChild() {
            return firstChild != null;
        }
    }
}

